package 链表;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

//https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08?tpId=295&tqId=1008897&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
//https://leetcode.cn/problems/sort-list/description/
public class BM12_单链表的排序 {

	public static void main(String[] args) {

	}
	
	/*
	 * 方法一：归并排序（推荐使用）
	 * 	step 1：首先判断链表为空或者只有一个元素，直接就是有序的。
		step 2：准备三个指针，快指针right每次走两步，慢指针mid每次走一步，前序指针left每次跟在mid前一个位置。三个指针遍历链表，当快指针到达链表尾部的时候，慢指针mid刚好走了链表的一半，正好是中间位置。
		step 3：从left位置将链表断开，刚好分成两个子问题开始递归。
		step 4：将子问题得到的链表合并，参考合并两个有序链表。
	 */
	public ListNode sortInList (ListNode head) {
		//链表为空或者只有一个元素，直接就是有序的
		if(head == null || head.next == null) {
			return head;
		}
		ListNode left = head;
        ListNode mid = head.next;
        ListNode right = head.next.next;
        //右边的指针到达末尾时，中间的指针指向该段链表的中间
        while(right != null && right.next != null) {
        	left = left.next;
        	mid = mid.next;
        	right = right.next.next;
        }
		 //左边指针指向左段的左右一个节点，从这里断开
        left.next = null;
        //分成两段排序，合并排好序的两段
        return merge(sortInList(head), sortInList(mid));
	}
	
	private ListNode merge(ListNode pHead1,ListNode pHead2) {
		//一个已经为空了，直接返回另一个
		if(pHead1 == null) return pHead2;
		if(pHead2 == null) return pHead1;
		//加一个表头
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        //两个链表都要不为空
        while(pHead1 != null && pHead2 != null) {
        	//取较小值的节点
        	if(pHead1.val <= pHead2.val) {
        		cur.next = pHead1;
        		//只移动取值的指针
        		pHead1 = pHead1.next;
        	}else {
        		cur.next = pHead2;
        		//只移动取值的指针
        		pHead2 = pHead2.next;
        	}
        	//指针后移
        	cur = cur.next;
        }
        //哪个链表还有剩，直接连在后面
    	if(pHead1 != null) {
    		cur.next = pHead1; 
    	}else {
    		cur.next = pHead2;
    	}
    	//返回值去掉表头
    	return head.next;
	}

	/**
	 * 方法二：转化为数组排序（扩展思路）
	 * step 1：遍历链表，将节点值加入数组。
	 * step 2：使用内置的排序函数对数组进行排序。
	 * step 3：依次遍历数组和链表，按照位置将链表中的节点值修改为排序后的数组值。
	 */
	 public ListNode sortInList01(ListNode head) {
	        List<Integer> nums = new ArrayList<>();
	        ListNode p = head;
	        while (p != null) {
	        	nums.add(p.val);
	        	p = p.next;
			}
	        
	        Collections.sort(nums);
	        p = head;
	        for(int i = 0;i< nums.size();i++) {
	        	p.val = nums.get(i);
	        	p = p.next;
	        }
	        return head;
	 }
}
